## Problem 63 solution - MB
##
## I was hoping for another fun one :) The problem is to count all the 
## numbers which are both n digits and nth powers., e.g. 9^1 = 9.
## Things we know: The top limit on these numbers for all n values is 10^n,
## which is always n+1 digits long. We can decide on a bottom limit by taking
## the ceiling function of the n-root of 10^(n-1), the first n digit number.
## We can add up (top limit - bottom limit) until our top and bottom limit
## finally meet at some value of n (10^(n-1) increases faster than 9^(n-1)).
## 
## Another method (which I did not use in my initial solution) takes on
## the problem from a different angle. It realizes that our n-root numbers
## will always be less than 10 (as max is 10^n), and that for each value
## x from 1 to 9 will eventually reach a point where x^n <= 10^(n-1) for
## some value of n.  If we set these two sides equal, we can calculate the
## crossover point, n, with logarithms.
## x^n = 10^(n-1)
## x^n = (10^n)(0.1)
## n*log(x) = n*log(10) + log(0.1)
## n(log(x) - log(10)) = log(0.1)
## n(log(x/10)) = log(0.1)
## n = log(0.1)/(log(x/10))
## If we take the floor of this function for all values of x (1-9), we will
## get the number of values of n for which 9^n > 10^(n-1). Totaling
## those numbers gives us the answer to the problem.
## Thanks to Alvaros from project euler for the first writeup of this method.
##
## Both methods are trivially fast in this case, althogh the logarithm-based
## version uses less than half as many iterations.

from math import ceil

n=1
cnt=0
while 9**n > 10**(n-1):
	cnt+= 10-ceil((10**(n-1))**(1/n))
	n+=1
print(cnt)
